package array.leetcode.easy;

/**
 * @author bruin_du
 * @description 旋转数组的最小数字
 * @date 2022/5/18 18:44
 **/
public class Offer11_MinArray {
    int choice = 1;
    public int minArray(int[] numbers) {
        //使用二分查找，因为数组本身是有序的，只是经过了几次旋转
        //把处于交界处的点称为旋转点
        if(choice == 1){
            int left = 0,right = numbers.length - 1;
            //当left == right的时候就跳出循环
            //此时left和right都指向旋转点的值
            //不能保证为旋转点对应的位置,但是能保证值是相等的
            //因为后面mid指向的值和right指向的值相等的时候
            while(left < right){
                int mid = (right - left >> 1) + left;
                //mid指向的值大于right指向的值
                //说明旋转点肯定在[mid + 1,right]之中
                if(numbers[mid] > numbers[right])
                    left = mid + 1;
                //mid指向的值小于right指向的值
                //说明旋转点肯定在[left,mid]之中
                else if(numbers[mid] < numbers[right])
                    right = mid;
                //当两者指向的值相等的时候
                //无法判断 mid 在哪个排序数组中，即无法判断旋转点在 [left, m] 还是 [m + 1, right] 区间中
                //此时不能根据二分查找的步骤
                //可以逐个减小right,缩小区间来查找旋转点,但是这里不能准确找到旋转点,只能保证找到与旋转点相等的值

                //当没有值和旋转点相等时,right不会逐渐减小,此时会根据二分来缩小区间,从而准确找到旋转点

                //当有元素和旋转点相等时,right会减小,虽然跨过了旋转点,但是数组中还是有与之相等的值
                //而且根据二分缩小范围,一定可以锁定与之相等的值,虽然不是旋转点

                //其实此时可以不再使用二分查找,极端情况下比如所有元素相等时,时间复杂度会退化为O(n)
                //此时可以在已经判断过的区间上使用遍历查找的方法，比如写法二
                else
                    right--;
            }
            return numbers[left];
        }

        //写法二：在判断有相等元素时，主动放弃二分查找，在判断过后的区间上使用遍历查找
        if(choice == 2){
            int left = 0,right = numbers.length - 1;
            while(left < right){
                int mid = (right - left >> 1) + left;
                if(numbers[mid] > numbers[right])
                    left = mid + 1;
                else if(numbers[mid] < numbers[right])
                    right = mid;
                else{
                    int min = numbers[left];
                    for (int i = left + 1; i <= right; i++) {
                        if(numbers[i] < min) min = numbers[i];
                    }
                    return min;
                }
            }
            return numbers[left];
        }
        return -1;
    }
}
